package com.zk.algorithm.tree;

import com.zk.algorithm.bean.BinaryTreeNode;
import com.zk.algorithm.factory.TreeFactory;

import java.util.Stack;

/**
 * 迭代版本的中序遍历
 *
 * 1) Create an empty stack S.
 2) Initialize current node as root
 3) Push the current node to S and set current = current->left until current is NULL
 4) If current is NULL and stack is not empty then
 a) Pop the top item from stack.
 b) Print the popped item, set current = popped_item->right
 c) Go to step 3.
 5) If current is NULL and stack is empty then we are done.
 */
public class IterativeInOrder {

    public void inorderIterative(BinaryTreeNode root) {
        if (root == null)
            return;

        Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
        BinaryTreeNode curr = root;

        // traverse the tree
        while (curr != null || s.size() > 0) {

            /* Reach the left most Node of the
            curr Node */
            while (curr !=  null) {
                /* place pointer to a tree node on
                   the stack before traversing
                  the node's left subtree */
                s.push(curr);
                curr = curr.getLeft();
            }

            /* Current must be NULL at this point */
            curr = s.pop();

            System.out.print(curr.getVal() + " ");

            /* we have visited the node and its
               left subtree.  Now, it's right
               subtree's turn */
            curr = curr.getRight();
        }
    }

    public static void main(String...args) {
       new IterativeInOrder().inorderIterative(TreeFactory.buildCompleteTree(9));
    }

}
